Leftmost column with at least a one¶
Time: O(M+N); Space: O(1); medium
This problem is a relatively new problem and is a cool problem to think about. Since this is a interactive problem, it makes for a interesting solution. It is on the edge of an easy-medium category problem depending on how you come up with the solution. Okay enough talking, let us get to it. Problem Description -
A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.
Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1.
You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface: * BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed). * BinaryMatrix.dimensions() returns a list of 2 elements [m, n], which means the matrix is m * n.
Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.
Example 1:
Input: mat = [[0,0],[1,1]]
Output: 0
Example 2:
Input: mat = [[0,0],[0,1]]
Output: 1
Example 3:
Input: mat = [[0,0],[0,0]]
Output: -1
Example 4:
Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1
Try the problem before looking at the solution. The solution is rather easy if you think about it enough.
Okay, so it is important to note that in the problem we need to 1. Reduce the number of calls to binaryMatrix.get() function, hence we need to think of minimizing the number of calls. 2. It would be easy to traverse all the blocks from the left side, but this would increase the number of calls to the get() function. 3. Every row is sorted. Hence every row starts from 0 and if it has a one, ends in 1. For example, if a row has 3 0’s and 2 1’s , it would be [0 0 0 1 1] . This is important as it let’s us understand that for every row, if we go from the last index to the first and keep a variable for the leftMostColumn we found a 1 in, we can solve this. 4. We can also understand that say we are at the right-most cell, and the cell is 0, we can go down, since we know that there is no 1 on our left. The 3rd and 4th point are important to understand as that is how our solution is optimal. Now that we understand this, let us go through a example.
Here we can see that our start is on the right top most element, every time we see a 0 , we go down, since we know that no 1 occurs on our left. When we see a 1, we add it to a variable ( so we remember it) and go left since there could be a another 1 to its left, then we a see a 0 and go down and so on. If we are on the last row and see a 0, we can stop since we know we have reach the left most element. Now that makes it O(ROWS +COLUMN) or O(M+N) for short in worst case.
[3]:
class BinaryMatrix(object):
def __init__(self, mat):
self.matr = matr
def get(self, row, col):
pass
def dimensions(self):
pass
[4]:
class Solution1(object):
"""
Time: O(M+N)
Space: O(1)
"""
def leftMostColumnWithOne(self, binaryMatrix):
"""
:type binaryMatrix: BinaryMatrix
:rtype: int
"""
m, n = binaryMatrix.dimensions()
r, c = 0, n-1
while r < m and c >= 0:
if not binaryMatrix.get(r, c):
r += 1
else:
c -= 1
return c+1 if c+1 != n else -1
[5]:
s = Solution1()
# mat = [[0,0],[1,1]]
# matr = binaryMatrix(mat)
# assert s.leftMostColumnWithOne(matr) == 0
# mat = [[0,0],[0,1]]
# matr = binaryMatrix(mat)
# assert s.leftMostColumnWithOne(matr) == 1
# mat = [[0,0],[0,0]]
# matr = binaryMatrix(mat)
# assert s.leftMostColumnWithOne(matr) == -1
# mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
# matr = binaryMatrix(mat)
# assert s.leftMostColumnWithOne(matr) == 1